//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 1 <= n <= 2 * 10⁴
// 0 <= height[i] <= 10⁵
//
//
// Related Topics 栈 数组与矩阵 双指针 动态规划 单调栈 👍 4266 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function trap(height: number[]): number {
    //? 单调栈法

    //? 非严格单调递减呗 为了保证左边能够跟右边做成窝窝 遇到地址再计算雨量 当然还需要注意头尾不能接雨因为缺了左/右 尾递减不需要处理 递增则本就需要处理
    let stack : number[] = []
    let res : number = 0
    stack.push(0)
    for (let i = 1; i < height.length; i ++) {
        //? 遇到不递减的
        while (stack.length > 0 && height[stack[stack.length - 1]] < height[i]) {
            //? 有窝窝的判断 保证左边高度也大于栈顶高度
            if (stack.length > 1 && height[stack[stack.length - 2]] > height[stack[stack.length - 1]]) {
                //? 因为横向计算 所以需要求出左右柱子最小值再减去中间窝窝的高度 再乘以中间的gap 因为有可能中间窝窝不止1个宽度
                res += (Math.min(height[stack[stack.length - 2]], height[i]) - height[stack[stack.length - 1]]) * (i - stack[stack.length - 2] - 1)
            }
            stack.pop()
        }
        stack.push(i)
    }
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
